Asynchronous Transfer Mode (ATM) provides connection-oriented transport of data across a network of switching devices. Frames of data are segmented into fixed-size data cells, having a 5-byte cell header and 48-byte payload, for transmission across the network. The term "frame" will be used herein interchangeably with the term "packet". These data cells are transported on a Virtual Channel Connection (VCC) identified by the concatenation of a 16-bit Virtual Channel Identifier carried in the cell header.
The 12-bit VPI value is used for transport between switches (i.e., Node-to-Node Interface or NNI) and the 8-bit VPI value is used for transport between a user-device and a switch (User-to-Network Interface or UNI). The VCC may transport data between two points or from a single point (i.e., root) to multiple points (i.e., leaves). The former is called point-to-point connection and the latter is a point-to-multipoint connection. The segment of an end-to-end connection between two devices is known as a link. The activity of routing a received cell from an inbound link to one or more outbound links associated with the connection is called switching.
VCCs may be bundled into a Virtual Path Connection (VPC) for transport through a sequence of network switches. The VPC is identified by the VPI value in the cell header. Information is stored in each network switch to indicate whether cells associated with a particular VPI value should all be switched in common (VP switching) according to the VPI value or, should be switched individually according to the concatenation of VPI and VCI values (VC switching).
At the endpoints of an ATM connection, a function called the ATM Adaptation Layer (AAL) is provided as an interface between ATM user applications and the cell-based ATM transport. One such ATM Adaptation Layer is AAL-5, which provides an interface for transport of variable length frames of data (as are common in Local Area Network (LAN) and Frame-Relay environments). An important function of AAL-5 is the segmentation of frames into ATM cells at the network ingress, and the reassembly of cells into frames at the network egress.
An ATM connection is associated with one of five service categories describing the method to be used for traffic management. One of these methods is called Unspecified Bit Rate (UBR), which is intended for best-effort transport of data. Such a method does not guarantee delivery of data. Specifically, when congestion occurs, the ATM network may discard cells. However, there is no standard method for performing traffic management of UBR traffic. When a cell is discarded, the destination (i.e., the endpoint) is unable to reassemble the cell into the associated frame. Higher programming layers enable recovery from the loss of the frame. An example of such a higher layer is the Transmission Control Protocol (TCP) of the Internet Protocol (IP). The term "Packet-Discard" will be used hereinafter to refer to the dropping or discarding of frames in the network.
One approach to manage Packet-Discard is Partial Packet Discard (PPD), which discards one or more data cells of a frame, without discarding all cells of the frame. When a data cell is received at a network switch, the switch determines whether the data cell should be dropped due to congestion. However, assuming that (i) an average of 10 percent of data cells are dropped over time, (ii) an average frame contains 10 cells and (iii) the distribution of dropped cells is uniform, the rate of incomplete frame reception at the destination will be very high. This will result in a high volume of retransmission requests and an increase in network congestion.
A better approach to manage Packet-Discard is Early Packet Discard (EPD), which is generally implemented for traffic on each AAL-5/UBR VCC. When a first cell or frame is received at a network switch, queues are examined to determined whether congestion has reached a point where dropping of cells may soon be necessary. If so, the network switch discards the first cell and all subsequent cells associated with the frame. This is accomplished by marking VCC information, in the network switch, with an indication (frame-drop marker) that all data cells of the marked frame should be discarded. The arriving data cells of the marked frame are continuously discarded until an end-of-frame cell is received, at which time the frame-drop marker is removed.
A problem arises when the cell containing the end-of-frame marker has been lost, as a result of transmission error or congestion at an earlier switch not performing the EPD function. In such a case, the subsequent frame on the particular VCC will also be discarded. This situation is, however, assumed to be an infrequent occurrence. Accordingly, EPD allows the network switch to avoid forwarding partial frames that are of no use to the recipient, to reduce the number of frames requiring retransmission, and to reduce congestion of the switching nodes.
However, in some nodes, AAL-5/UBR traffic is carried on Virtual Path (VP) connections, and VP switching is performed at the switching nodes. In this case, there is no convenient way to perform EPD. Specifically, when VP switching is performed, the switch examines only the VPI field of the cell header. All cells having the same VPI value are switched to a common outbound VP link (or set of VP links in the case of point-to-multipoint system). The switching tables used for VP switching do not contain any reference to individual VCCs. As a result, there is no place to record information that all data cells of a frame belonging to a particular VCC should be dropped.
Moreover, there is no method to recognize when a first cell of a frame (i.e., beginning-of-frame cell) has been received. As ATM cells do not include a beginning-of-frame marker, information that a first cell of a frame has been received is inferred from information that the previous cell, with the same VCC, was an end-of-frame cell. This is not a problem when Virtual Channel (VC) switching is employed because there is information about individual VCCs. However, it is problematic when VP switching is performed. In the latter case, there is currently no way to retain information as to whether a previous data cell, with the same VCC, was an end-of-frame cell.
One possible solution is to employ a look up table, associated with each VP passing through the switch. The table will contain all possible values of VCI for that VP. When a cell is received, the table is searched or indexed to identify an entry associated with the VCI value in the cell header. The entry can be used to store information that a previous cell with the VCI value was an end-of-frame cell and that data cells associated with the frame are to be discarded. However, the very purpose of introducing VP switching, is to avoid the necessity of a large table containing all VCI values. This solution defeats the intended purpose of VP switching.
An alternative approach is to maintain a database (e.g., a tree structure), associated with each VP connection. The tree structure contains an entry for each VCI for which a cell has been received, but an end-of-frame cell has not been received. Conceptually, this is a dynamic representation of each frame passing through the switch. When an arriving data cell does not have a corresponding entry in the database, the network switch can infer that the data cell is a beginning-of-frame cell (unless of course, a data cell was dropped in an earlier switch). In this case, an entry in the database is created. It is then determined whether the level of congestion is such that EPD should be performed. If so, the database entry is marked, and subsequent cells of the frame will be discarded. When the end-of-frame cell is received, the database entry is cleared or destroyed. Again, it is possible that an end-of-frame cell may have been discarded at an earlier node, which will result in discard of the subsequent frame.
The problem with this implementation is the number of steps required to perform a search to find a particular database entry. In order to be effective, the search must be completed within the time required to switch the cell. However, it is difficult to guarantee that the required number of search steps can be performed within the time period.
In view of the foregoing, there is a need to provide a better approach to managing Packet-Discard, in the event of data congestion at a network switch. There is also a need to provide such an approach with minimal hardware and software at the network switch and with the capability of performing a Packet-Discard operation within the time allotted for a switching operation.
Accordingly, it is an object of the invention to provide a method and apparatus for managing Packet-Discard to alleviate data congestion at the ATM switched.
It is a further object of the invention to provide at each ATM switch or switch adapter, an addressable table for tracking cells of each frame received at the network switch.
Another object of the invention is to provide a table as described above which requires minimal storage space and can be incorporated into an ATM switch or adapter.
A further object of the invention is to employ hashing techniques to minimize the size of the table and the time for searching a record stored in the table.
Another object of the invention is to provide the above features in an ATM switch that employs Virtual Path (VP) switching.